package com.zk.algorithm.stackandqueue;

import com.zk.algorithm.annotation.JianZhiOffer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 两个栈 (FILO) 实现队列 (FIFO)
 *
 * - push 总往 q1 push
 * - pop 将 q1 中的元素移至 q2 (直至剩下一个)，然后 pop q1，然后 q1 和 q2 交换角色
 *
 * @author zk
 */
@JianZhiOffer
public class ImplementStackUsingQueues {

    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();

    private int top;

    // =============================
    // O(1)
    // =============================

    // Push element x onto stack.
    public void push(int x) {
        q1.add(x);
        top = x;
    }

    // =============================
    // O(n)
    // =============================

    // Removes the element on top of the stack.
    public void pop() {
        while (q1.size() > 1) {
            top = q1.remove();
            q2.add(top);
        }

        q1.remove();

        // q1 和 q2 交换
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    // Return whether the stack is empty.
    public boolean isEmpty() {
        return q1.isEmpty();
    }

    // Get the top element.
    public int peek() {
        return top;
    }

}
